//N皇后
https://leetcode.cn/problems/n-queens/

class Solution {
public:
    typedef pair<int,int> PII;
    vector<PII> path;
    vector<vector<PII>> tmp;
    int _n;
    int y_pos[3] = {-1,0,1};

    vector<vector<string>> solveNQueens(int n) 
    {
        _n = n;
        dfs(0);
        vector<vector<string>> ret(tmp.size(),vector<string>(n,string(n,'.')));
        int i = 0;
        for(auto& e : tmp)
        {
            for(auto& ee: e)
            {
                ret[i][ee.first][ee.second] = 'Q';
            }
            i++;
        }

        return ret;
    }

    void dfs(int level)
    {
        if(level == _n)
        {
            tmp.push_back(path);
            for(auto e : path)
            {
                cout << e.first << " " << e.second << " ";
            }
            cout << endl;
            return;
        }

        for(int i = 0; i < _n; i++)
        {
            int x = level, y = i;
            if(judge(x,y))
            {
                path.push_back(make_pair(x,y));
                dfs(level + 1);
                path.pop_back();
            }
        }
    }

    bool judge(int line, int column)
    {
        for(int i = 0; i < 3; i++)
        {
            int x = line, y = column;
            while(x >= 0 && y >= 0 && y < _n)
            {
                for(auto e : path)
                {
                    if(e.first == x && e.second == y) return false;
                }
                x += -1; y += y_pos[i];
            }
        }
        return true;
    }

};